package com.fr.lintcode;

public class Q795 {

	/**
	 * @param m: the row
	 * @param n: the column
	 * @return: the possible unique paths
	 */
	int count = 0;

	public int uniquePaths(int m, int n) {
		// Write your code here
		if (m == 0 || n == 0) {
			return 0;
		}
		boolean reach[][] = new boolean[m][n];
		search(0, 0, m, n, reach);
		return count;
	}

	private void search(int i, int j, int m, int n, boolean[][] reach) {
		if (i == m - 1 && j == n - 1) {
			count++;
			return;
		}
		reach[i][j] = true;
		if (i - 1 >= 0 && !reach[i - 1][j]) {
			search(i - 1, j, m, n, reach);
		}
		if (i + 1 < m && !reach[i + 1][j]) {
			search(i + 1, j, m, n, reach);
		}
		if(j -1 >=0 && !reach[i][j - 1]) {
			search(i, j - 1, m, n, reach);
		}
		if (j + 1 < n && !reach[i][j + 1]) {
			search(i, j + 1, m, n, reach);
		}
		reach[i][j] = false;
	}

}
